package history

func quickSort(nums []int) {
	sort(nums, 0, len(nums)-1)
}

func sort(nums []int, low, high int) {
	if low < high {
		var left = low
		var right = high
		var povitVal = nums[low]

		for left < right {
			for left < right && nums[right] > povitVal {
				right--
			}
			if left < right {
				nums[left], nums[right] = nums[right], nums[left]
				left++
			}
			for left < right && nums[left] < povitVal {
				left++
			}
			if left < right {
				nums[left], nums[right] = nums[right], nums[left]
				right--
			}
		}
		nums[left] = povitVal
		sort(nums, low, left-1)
		sort(nums, left+1, high)
	}
}
